/*
*

一个音乐会总共有 n 排座位，编号从 0 到 n - 1 ，每一排有 m 个座椅，编号为 0 到 m - 1 。你需要设计一个买票系统，针对以下情况进行座位安排：

同一组的 k 位观众坐在 同一排座位，且座位连续 。
k 位观众中 每一位 都有座位坐，但他们 不一定 坐在一起。
由于观众非常挑剔，所以：

只有当一个组里所有成员座位的排数都 小于等于 maxRow ，这个组才能订座位。每一组的 maxRow 可能 不同 。
如果有多排座位可以选择，优先选择 最小 的排数。如果同一排中有多个座位可以坐，优先选择号码 最小 的。
请你实现 BookMyShow 类：

BookMyShow(int n, int m) ，初始化对象，n 是排数，m 是每一排的座位数。
int[] gather(int k, int maxRow) 返回长度为 2 的数组，表示 k 个成员中 第一个座位 的排数和座位编号，这 k 位成员必须坐在 同一排座位，且座位连续 。换言之，返回最小可能的 r 和 c 满足第 r 排中 [c, c + k - 1] 的座位都是空的，且 r <= maxRow 。如果 无法 安排座位，返回 [] 。
boolean scatter(int k, int maxRow) 如果组里所有 k 个成员 不一定 要坐在一起的前提下，都能在第 0 排到第 maxRow 排之间找到座位，那么请返回 true 。这种情况下，每个成员都优先找排数 最小 ，然后是座位编号最小的座位。如果不能安排所有 k 个成员的座位，请返回 false 。

示例 1：

输入：
["BookMyShow", "gather", "gather", "scatter", "scatter"]
[[2, 5], [4, 0], [2, 0], [5, 1], [5, 1]]
输出：
[null, [0, 0], [], true, false]

解释：
BookMyShow bms = new BookMyShow(2, 5); // 总共有 2 排，每排 5 个座位。
bms.gather(4, 0); // 返回 [0, 0]

	// 这一组安排第 0 排 [0, 3] 的座位。

bms.gather(2, 0); // 返回 []

	// 第 0 排只剩下 1 个座位。
	// 所以无法安排 2 个连续座位。

bms.scatter(5, 1); // 返回 True

	// 这一组安排第 0 排第 4 个座位和第 1 排 [0, 3] 的座位。

bms.scatter(5, 1); // 返回 False

	// 总共只剩下 1 个座位。

提示：

1 <= n <= 5 * 104
1 <= m, k <= 109
0 <= maxRow <= n - 1
gather 和 scatter 总 调用次数不超过 5 * 104 次。

  - @author ala
  - @date 2024-09-29 12:15
*/
package segment_tree

import (
	"math/bits"
)

type SegmentTreeMin struct {
	tree []int
	N, M int
}
type SegmentTreeSum struct {
	tree []int
	N, M int
}

type BookMyShow struct {
	sts           *SegmentTreeSum //	区间极小
	stm           *SegmentTreeMin //	区间和
	pos           []int           //	指向每一行当前空位
	N, M, minFull int             //	minFill：指向从左往右第一个未满的行（Scatter扫描用）
}

func Constructor(n int, m int) BookMyShow {
	mbs := BookMyShow{}
	mbs.stm = buildSegmentTreeMin(n, m)
	mbs.sts = buildSegmentTreeSum(n, m)
	mbs.pos = make([]int, n)
	mbs.minFull, mbs.N, mbs.M = -1, n, m
	return mbs
}

func (this *BookMyShow) Gather(k int, maxRow int) []int {
	//	直接返回[0, maxRow]中连续空位 >= k 的行号
	i := this.stm.Query(maxRow, k)
	if i == -1 {
		return []int{}
	}
	res := []int{i, this.pos[i]}

	this.pos[i] += k
	this.stm.Incr(i, k)
	this.sts.Incr(i, k)

	return res
}

func (this *BookMyShow) Scatter(k int, maxRow int) bool {
	//	前maxRow行（含maxRow）的总座位数 - 已经卖出的座位数 = 前maxRow行剩余座位数
	d := (maxRow+1)*this.M - this.sts.Query(maxRow)
	if d < k {
		return false
	}

	//	贪心的坐满每一行
	for i := this.minFull + 1; i <= maxRow; i++ {
		_d := min(this.M-this.pos[i], k)
		k -= _d

		this.pos[i] += _d
		this.sts.Incr(i, _d)
		this.stm.Incr(i, _d)
		//	更新minFull
		if this.pos[i] == 0 {
			this.minFull = i
		}
		if k == 0 {
			break
		}
	}
	return true
}

/************************************************************************************
 *	区间极小线段树
 ************************************************************************************/
func buildSegmentTreeMin(N, M int) *SegmentTreeMin {
	stm := &SegmentTreeMin{}
	stm.N, stm.M = N, M
	//	没太搞明白，为什么灵神这里是N-1，而不是N
	l := bits.Len(uint(N - 1))
	l = 2 << l
	stm.tree = make([]int, l)
	return stm
}

func (stm *SegmentTreeMin) Incr(i, k int) {
	stm.incr(i, k, 0, stm.N-1, 1)
}
func (stm *SegmentTreeMin) incr(i, k, s, t, p int) {
	if s == t {
		stm.tree[p] += k
		return
	}
	m := s + (t-s)>>1
	if i <= m {
		stm.incr(i, k, s, m, p<<1)
	} else {
		stm.incr(i, k, m+1, t, p<<1+1)
	}
	stm.tree[p] = min(stm.tree[p<<1], stm.tree[p<<1+1])
}

func (stm *SegmentTreeMin) Query(i, k int) int {
	return stm.query(0, i, k, 0, stm.N-1, 1)
}
func (stm *SegmentTreeMin) query(l, r, k, s, t, p int) int {
	_k := stm.M - stm.tree[p]
	if _k < k {
		return -1
	}
	if s == t {
		return s
	}
	m := s + (t-s)>>1
	if l <= m {
		res := stm.query(l, r, k, s, m, p<<1)
		if res != -1 {
			return res
		}
	}
	if r > m {
		res := stm.query(l, r, k, m+1, t, p<<1+1)
		if res != -1 {
			return res
		}
	}
	return -1
}

/************************************************************************************
 *	区间和线段树
 ************************************************************************************/
func buildSegmentTreeSum(N, M int) *SegmentTreeSum {
	sts := &SegmentTreeSum{}
	sts.N, sts.M = N, M
	l := bits.Len(uint(N - 1))
	l = 2 << l
	sts.tree = make([]int, l)
	return sts
}
func (sts *SegmentTreeSum) Incr(i, k int) {
	sts.incr(i, k, 0, sts.N-1, 1)
}
func (sts *SegmentTreeSum) incr(i, k, s, t, p int) {
	if s == t {
		sts.tree[p] += k
		return
	}
	m := s + (t-s)>>1
	if i <= m {
		sts.incr(i, k, s, m, p<<1)
	} else {
		sts.incr(i, k, m+1, t, p<<1+1)
	}
	sts.tree[p] = sts.tree[p<<1] + sts.tree[p<<1+1]
}
func (sts *SegmentTreeSum) Query(i int) int {
	return sts.query(0, i, 0, sts.N-1, 1)
}
func (sts *SegmentTreeSum) query(l, r, s, t, p int) int {
	if s >= l && t <= r {
		return sts.tree[p]
	}
	m, sum := s+(t-s)>>1, 0
	if l <= m {
		sum += sts.query(l, r, s, m, p<<1)
	}
	if r > m {
		sum += sts.query(l, r, m+1, t, p<<1+1)
	}
	return sum
}
